package 回文串;

public class test3 {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        // 数组i,j就是从下标为i到下标为j是否满足回文
        boolean[][] dp = new boolean[n][n];
        for(int i=n-1;i>=0;i--){
            for (int j = i; j < n; j++) {
                // 分为两种情况 相等和不相等
                if(s.charAt(i)==s.charAt(j)){
                    // 还要分为两种,一种是i和j之间有其他的字符,判定中间也是否为回文
                    // 另一种是两个之间没有,那就直接确定为回文
                    dp[i][j] = i+1<j?dp[i+1][j-1]:true;
                }else dp[i][j] = false;
            }
        }
        // 遍历结果
        for (int i = 0; i < n-1; i++) {
            for (int j = i; j < n-1; j++) {
                if(dp[0][i]&&dp[i+1][j]&&dp[j+1][n-1]) return true;
            }
        }
        return false;
    }
}
